package com.majie.algorithm.sort;

import com.majie.common.SwapUtils;

/**
 * 插入排序
 * <p>
 * 类似斗地主的起牌
 * <p>
 * <p>
 * 时间复杂度
 * 最好情况下，数组已经是有序的，每插入一个元素，只需要考查前一个元素，因此最好情况下，插入排序的时间复杂度为O(N)
 * <p>
 * 在最坏情况下，数组完全逆序，插入第2个元素时要考察前1个元素，插入第3个元素时，要考虑前2个元素，……，插入第N个元素，要考虑前 N - 1 个元素。
 * 因此，最坏情况下的比较次数是 1 + 2 + 3 + ... + (N - 1)，等差数列求和，结果为 N^2 / 2，所以最坏情况下的复杂度为 O(N^2)。
 * <p>
 * <p>
 * 少于16个元素的时候使用插入排序快
 *
 * @author majie
 * @date 2018/5/8.
 */
public class InsertSort {


    private static void sort(int[] arr, int left, int right) {

        for (int i = left; i <= right; i++) {

            //只需要比较i左边的数
            for (int j = i; j > left; j--) {

                //比较j和j-1
                if (arr[j] < arr[j - 1]) {
                    SwapUtils.swap(arr, j, j - 1);
                } else {
                    break;
                }
            }
        }
    }


    /**
     * 测试
     *
     * @param args
     */
    public static void main(String[] args) {
        int[] arr = {10, 6, 8, 3, 6, 5, 9, 4, 3, 1};
        sort(arr, 0, arr.length - 1);
        for (int i : arr) {
            System.out.print(i + " ");
        }
    }

}
